package com.xinwei.leetcode.二叉树;


import java.util.*;

// https://leetcode-cn.com/problems/binary-search-tree-iterator/
public class _173_二叉搜索树迭代器 {
    /**
     * 递归实现：具体思路和官解差不多，但不知道为什么时间花多好多
     * @return
     */
//    ArrayList<Integer> list;
//    Integer index;
//    public _173_二叉搜索树迭代器(TreeNode root) {
//        index = -1;
//        list = new ArrayList<>();
//        inorderTraversal(root);
//        for (Integer integer : list) {
//            System.out.println(integer);
//        }
//    }
//
//    public int next() {
//        if (hasNext()) return list.get(++index);
//        return 0;
//    }
//
//    public boolean hasNext() {
//        return list.size() > index + 1;
//    }
//
//    public void inorderTraversal(TreeNode root) {
//        if (root == null) return;
//        inorderTraversal(root.left);
//        list.add(root.val);
//        inorderTraversal(root.right);
//    }
//

    /**
     * 迭代实现
     * @param root
     */
    private Deque deque;
    private TreeNode cur;
    public _173_二叉搜索树迭代器(TreeNode root) {
        deque = new LinkedList<TreeNode>();
        cur = root;
    }

    public int next() {
        while (cur != null) {
            deque.push(cur);
            cur = cur.left;
        }
        cur = (TreeNode) deque.pop();
        int result = cur.val;
        cur = cur.right;
        return result;
    }

    public boolean hasNext() {
        return (cur != null || !deque.isEmpty());
    }
}
